package day_2022_12_to_3.year2023;

import java.util.Arrays;

/**
 * @author haomin
 * @date 2023/02/21 21:02
 **/
public class Day2_21_Num1326 {
    class Solution {
        public int minTaps(int n, int[] ranges) {
            int[] minNumArray = new int[n+1];
            Arrays.fill(minNumArray, -1);
            minNumArray[0] = 0;
            for(int i=0; i<ranges.length; i++) {
                if(ranges[i] == 0) {
                    continue;
                }
                int left = i-ranges[i]+1 >= 1 ? i-ranges[i]+1 : 1;
                int right = i+ranges[i] <= n ? i+ranges[i] : n;
                if(minNumArray[left-1] == -1) continue;
                for(int j=left; j<=right; j++) {
                    if(minNumArray[j] == -1 || minNumArray[left-1] + 1 < minNumArray[j]) {
                        minNumArray[j] = minNumArray[left-1] + 1;
                    }
                }
            }
            for(int k : minNumArray) {
                if(k == -1) return -1;
            }
            return minNumArray[n];
        }
    }
}